#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;

typedef int Vertex; /* 顶点编号类型 */
typedef struct BiGraphNode *BiGraph; /* 邻接矩阵表示的图 */
struct BiGraphNode {
    int n_u_verts; /* U点集顶点数 */
    int n_v_verts; /* V点集顶点数 */
    int m_edges; /* 边数 */
    bool **edge_matrix;/* 邻接矩阵 */
};
#define NIL -1 /* 顶点不存在时的返回值 */

void InitGraph(BiGraph bigraph, int u_size, int v_size);
void InsertEdge(BiGraph graph, Vertex u, Vertex v);
BiGraph BuildGraph();

/* 算法8-8：找二部图匹配的增广路径 FindAugmentingPath(bigraph, match, u, visited) */
bool FindAugmentingPath(BiGraph bigraph, Vertex match[], Vertex u,
                        bool visited[]) {
    bool ret;
    Vertex v;

    ret = false;
    for (v = 0; v < bigraph->n_v_verts; v++) { /* u的每个邻接点v */
        if (bigraph->edge_matrix[u][v] == true && visited[v] == false) {
            visited[v] = true;
            if (match[v] == NIL ||
            FindAugmentingPath(bigraph, match, match[v], visited) == true) {
                match[v] = u; /* u与v匹配 */
                ret = true;
                break;
            }
        }
    }
    return ret;
}
/* 算法8-8 结束 */

/* 算法8-7：求解二部图最大匹配的匈牙利算法 MaximumMatch(bigraph, match) */
int MaximumMatch(BiGraph bigraph, Vertex match[]) {
    int n, n_match;
    bool *visited;
    Vertex u, v;

    n = bigraph->n_v_verts; /* 点集V的顶点数 */
    visited = (bool *)malloc(sizeof(bool) * n);
    n_match = 0;
    for (v = 0; v < n; v++) {
        match[v] = NIL; /* 初始化，NIL表示未匹配 */
    }
    for (u = 0; u < bigraph->n_u_verts; u++) { /* 对U集合中的每个顶点 */
        for (v = 0; v < n; v++) {
            visited[v] = false; /* 初始化 */
        }
        if (FindAugmentingPath(bigraph, match, u, visited) == true) {
            n_match++; /* 从U顶点出发能找到增广路径，则匹配数加1 */
        }
    }
    return n_match;
}
/* 算法8-7 结束 */

int main(void) {
    BiGraph bigraph;
    Vertex *match;

    bigraph = BuildGraph();
    match = (Vertex *)malloc(sizeof(Vertex) * bigraph->n_u_verts);
    printf("最大匹配值 = %d\n", MaximumMatch(bigraph, match));

    return 0;
}

void InitGraph(BiGraph bigraph, int u_size, int v_size) {
    /* 初始化一个空的图 */
    bool *array;
    int i;
    Vertex u, v;

    bigraph->n_u_verts = u_size;
    bigraph->n_v_verts = v_size;
    bigraph->m_edges = 0;
    /* 声明二维数组graph->edge_matrix[U][V] */
    array = (bool *)malloc(sizeof(bool) * bigraph->n_u_verts * bigraph->n_v_verts);
    bigraph->edge_matrix = (bool **)malloc(sizeof(bool *) * bigraph->n_u_verts);
    for (i = 0; i < bigraph->n_u_verts; i++) {
        bigraph->edge_matrix[i] = &array[i * bigraph->n_v_verts];
    }
    for (u = 0; u < bigraph->n_u_verts; u++) {
        for (v = 0; v < bigraph->n_v_verts; v++) {
            bigraph->edge_matrix[u][v] = false;
        }
    }
}

void InsertEdge(BiGraph graph, Vertex u, Vertex v) {
    /* 向图中插入有向边<u,v> */
    graph->edge_matrix[u][v] = true;
    graph->m_edges++;
}

BiGraph BuildGraph() {
    BiGraph bigraph;
    int nu, nv, m, i;
    Vertex u, v;

    scanf("%d %d %d\n", &nu, &nv, &m);
    bigraph = (BiGraph)malloc(sizeof(struct BiGraphNode));
    InitGraph(bigraph, nu, nv);
    for (i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        InsertEdge(bigraph, u, v);
    }
    return bigraph;
}